package org.arithmetic.acm.primary;

import java.util.Scanner;

/**
 * Created by LUOLIANG on 2016/9/16.
 * 已知数组a和数组b中的数据元素按值非递减有序排列，现要求将a和b归并为一个新的数组c，且c中的数据元素任然按值非递减有序排列。请输出这个数组c。
 * 第一行包括两个整数n, m(1 <= n,m <= 10^5)，分别代表a，b两个数组的长度。
 * 第二行包括n个int整数，代表数组a的每一项。
 * 第三行包括m个int整数，代表数组b的每一项。
 * <p>
 * 输出只有一行，为数组c的每一项的值，中间用空格隔开。
 */
public class ArrayMerge {
    private static final int MAX_RANGE = 100000;

    public static void main(String[] args) {
        int[] arr1 = new int[MAX_RANGE];
        int[] arr2 = new int[MAX_RANGE];
        Scanner input = new Scanner(System.in);
        int arr1_range = input.nextInt();
        int arr2_range = input.nextInt();
        for (int i = 0; i < arr1_range; i++) {
            arr1[i] = input.nextInt();
        }
        for (int i = 0; i < arr2_range; i++) {
            arr2[i] = input.nextInt();
        }
        int[] arr3 = new int[arr1_range + arr2_range];
        int k = 0, j = 0;
        for (int i = 0; i < arr3.length; ) {

            while ((arr1[j] <= arr2[k] && k < arr2_range || arr2_range == k) && i < arr3.length) {
                if (j == arr1_range) {
                    break;
                }
                arr3[i++] = arr1[j++];
            }

            while ((arr1[j] > arr2[k] && j < arr1_range || arr1_range == j) && i < arr3.length) {
                if (k == arr2_range) {
                    break;
                }
                arr3[i++] = arr2[k++];
            }

        }
        for (int i = 0; i < arr3.length; i++) {
            System.out.print(i + 1 == arr3.length ? arr3[i] : arr3[i] + " ");
        }
    }
}//2 6 8 9 11 15 20      3 5 8 11
